package cn.pugle.oj.leetcode;

import cn.pugle.oj.catalog.DaiBi;
import cn.pugle.oj.catalog.DynamicProblem;

/**
 * Created by tzp on 15-10-20.
 * 最长回文子串
 * 程序不知道有没有问题，分析复杂度好像是n3方级的，但是方法递归调用太多了。
 * Time Limit Exceeded
 */
public class LC5_LongestPalindromicSubstring implements DaiBi, DynamicProblem {
    public String longestPalindrome(String s) {
        System.out.println(s.length());
        return longestPalindromeR(s, 0, s.length() - 1).toString();
    }

    public StringWithIndex longestPalindromeR(String str, int begin, int end) {
//        System.out.println("begin :" + begin + " ; end :" + end);
        if (isPalindromic(str, begin, end)) {
            return new StringWithIndex(str, begin, end);
        } else {
            StringWithIndex sub1 = longestPalindromeR(str, begin, end - 1);
            StringWithIndex sub2 = longestPalindromeR(str, begin + 1, end);
            return sub1.length() > sub2.length() ? sub1 : sub2;
        }
    }

    public boolean isPalindromic(String str, int begin, int end) {
        System.out.println(str.substring(begin, end + 1));
        while (begin < end) {
            if (str.charAt(begin) != str.charAt(end)) {
                return false;
            }
            begin++;
            end--;
        }
        return true;
    }

    public static class StringWithIndex {
        String nestedStr;
        int begin;
        int end;

        public StringWithIndex(String nestedStr, int begin, int end) {
            this.nestedStr = nestedStr;
            this.begin = begin;
            this.end = end;
        }

        public int length() {
            return end - begin + 1;
        }

        @Override
        public String toString() {
            return nestedStr.substring(begin, end + 1);
        }
    }

    public static void main(String[] args) {
        long beginTime = System.currentTimeMillis();
        System.out.println(new LC5_LongestPalindromicSubstring().longestPalindrome("abcdefghijklmn"));
//        System.out.println(new LongestPalindromicSubstring().longestPalindrome("civilwartestingwhetherthatnaptionoranynartionsoconceivedandsodedicatedcanlongendureWeareqmetonagreatbattlefiemldoftzhatwarWehavecometodedicpateaportionofthatfieldasafinalrestingplaceforthosewhoheregavetheirlivesthatthatnationmightliveItisaltogetherfangandproperthatweshoulddothisButinalargersensewecannotdedicatewecannotconsecratewecannothallowthisgroundThebravelmenlivinganddeadwhostruggledherehaveconsecrateditfaraboveourpoorponwertoaddordetractTgheworldadswfilllittlenotlenorlongrememberwhatwesayherebutitcanneverforgetwhattheydidhereItisforusthelivingrathertobededicatedheretotheulnfinishedworkwhichtheywhofoughtherehavethusfarsonoblyadvancedItisratherforustobeherededicatedtothegreattdafskremainingbeforeusthatfromthesehonoreddeadwetakeincreaseddevotiontothatcauseforwhichtheygavethelastpfullmeasureofdevotionthatweherehighlyresolvethatthesedeadshallnothavediedinvainthatthisnationunsderGodshallhaveanewbirthoffreedomandthatgovernmentofthepeoplebythepeopleforthepeopleshallnotperishfromtheearth"));
        System.out.println(System.currentTimeMillis() - beginTime);
    }
}
